package com.captain.special.二叉树.中等;

import com.captain.leetcode.TreeNode;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/21 23:07
 */
public class 最长路径 {
    int max;

    public static void main(String[] args) {
        System.out.println(new 最长路径().longestPath(TreeNode.spanningTree(new Integer[]{1, 2, 3, 4, null, 5, 6, null, 7, null, 8})));
    }

    public int longestPath(TreeNode root) {
        if (root == null) return 0;
        recur(root);
        return max;
    }

    public int recur(TreeNode node) {
        if (node.left == null && node.right == null) {
            return 0;
        }
        int leftSize = 0;
        int rightSize = 0;
        //求路径
        //左边路径
        if (node.left != null) {
            leftSize = recur(node.left) + 1;
        }
        //右边路径
        if (node.right != null) {
            rightSize = recur(node.right) + 1;
        }
        max = Math.max(max, leftSize + rightSize);
        return Math.max(leftSize, rightSize);
    }
}
